package interviewcoding.similarity;

import java.util.Random;

/**
 * 思路:一个字符串至少需要编辑（增删改）多少次才可以变成另一个字符串
 * 相似度：1 - （编辑次数）/  max( len(s1,s2)) ）
 */

public class Similarity {

    // 设定字符串在1000个字符以内
        static int N = 1010;
        static int [][] dp ;
        public static void main(String [] args){

            Random random = new Random();
            // 循环是10次，每次随机生成两个字符串
            int m = 10;
            while(m -- > 0) {
                // 创建dp数组
                dp = new int[N][N];
                // 字符串1的长度
                int len1 = random.nextInt(50) + 1;
                StringBuffer str1 = new StringBuffer();
                // 生成字符串1
                for(int i = 0 ; i < len1 ; i ++){
                    str1.append(random.nextInt(10));
                }
                // 字符串2的长度
                int len2 = random.nextInt(50) + 1;
                // 生成字符串2
                StringBuffer str2 = new StringBuffer();
                for(int i = 0 ; i < len2 ; i ++){
                    str2.append(random.nextInt(10));
                }

                // dp数组初始化
                for (int i = 0; i <= len2; i++) dp[0][i] = i;
                for (int i = 0; i <= len1; i++) dp[i][0] = i;

                // dp[i][j]的含义：s1的前i个字符变成s2的前j个字符至少需要编辑多少次
                for (int i = 1; i <= len1; i++) {
                    for (int j = 1; j <= len2; j++) {
                        // 删除操作：把s1[i]删掉之后s1[1-i]和s2[1-j]匹配，所以之前要先做到s1[1-(i-1)]和s2[1-j]匹配
                        //      即 dp[i-1][j] + 1
                        // 插入操作：插入之后s1[i]和s2[j]完全匹配，所以插入的就是s2[j],那填之前s1[1-i]与s2[1-(j-1)]匹配
                        //      即 dp[i][j-1] + 1
                        //
                        dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
                        if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                            // s1 的第i个字符与s2的第j个字符匹配 dp[i-1][j-1]
                            dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1]);
                        } else {
                            // 把s1[i] 修改成  s2[j] ,那么之前需要满足 dp[1-(i-1)][1-(j-1)]匹配
                            dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1] + 1);
                        }
                    }
                }
                // 相似度的公式：
                // similarity = 1 - (edit_distance) / (max(l1,l2))
                double similarity = 1 - ((double) dp[len1][len2]) / (Math.max(len1, len2));
                System.out.println("str1 = >" + str1.toString());
                System.out.println("str2 = >" + str2.toString());
                System.out.printf("相似度为=" + similarity);
                System.out.println();
            }
        }
}
